package com.cyy.test_t_6_;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Description 剑指Offer t_60 - 把二叉树打印成多行
 * 题目描述：
 * 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
 * @Author Crystal
 * @Date 2019/7/16 22:07
 * @Version 1.0
 **/
public class t_60 {
    /**
     * 定义二叉树
     */
    private static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;
        private TreeNode parent;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }
    }

    public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(pRoot == null) return result;
        Queue<TreeNode> layer = new LinkedList<>();
        ArrayList<Integer> layerList = new ArrayList<>();
        //放入根父节点到队列
        layer.add(pRoot);
        int start = 0, end = 1;
        //按顺序将左节点与右节点放入队列
        while(!layer.isEmpty()){
            //队列中数据出队列
            TreeNode cur = layer.poll();
            layerList.add(cur.val);
            //记录当前层节点已经出队列次数，每出一次加一
            start ++;
            //如果当前节点左孩子有值，则入队
            if(cur.left != null){
                layer.add(cur.left);
            }
            //如果当前节点右孩子有值，则入队
            if(cur.right != null){
                layer.add(cur.right);
            }
            //当前层所有数据都已经出队完毕
            if(start == end){
                end = layer.size(); //记录树下一层节点数，控制队列出队次数
                start = 0;
                result.add(layerList);
                layerList = new ArrayList<>(); //不能用clear，只能清空引用
            }
        }
        return result;
    }

    private static void assemble(TreeNode node,
                                 TreeNode left,
                                 TreeNode right,
                                 TreeNode parent) {
        node.left = left;
        node.right = right;
        node.parent = parent;
    }

    public static void main(String[] args) {
        test01();
    }

    //                            1
    //                  2                   3
    //             4         5          6          7
    //          8     9   10   11   12   13    14   15
    public static void test01() {
        TreeNode n1 = new TreeNode(1); // 12
        TreeNode n2 = new TreeNode(2); // 10
        TreeNode n3 = new TreeNode(3); // 14
        TreeNode n4 = new TreeNode(4); // 9
        TreeNode n5 = new TreeNode(5); // 11
        TreeNode n6 = new TreeNode(6); // 13
        TreeNode n7 = new TreeNode(7); // 15
        TreeNode n8 = new TreeNode(8); // 4
        TreeNode n9 = new TreeNode(9); // 2
        TreeNode n10 = new TreeNode(10); // 5
        TreeNode n11 = new TreeNode(11); // 1
        TreeNode n12 = new TreeNode(12); // 6
        TreeNode n13 = new TreeNode(13); // 3
        TreeNode n14 = new TreeNode(14); // 7
        TreeNode n15 = new TreeNode(15); // null

        assemble(n1, n2, n3, null);
        assemble(n2, n4, n5, n1);
        assemble(n3, n6, n7, n1);
        assemble(n4, n8, n9, n2);
        assemble(n5, n10, n11, n2);
        assemble(n6, n12, n13, n3);
        assemble(n7, n14, n15, n3);
        assemble(n8, null, null, n4);
        assemble(n9, null, null, n4);
        assemble(n10, null, null, n5);
        assemble(n11, null, null, n5);
        assemble(n12, null, null, n6);
        assemble(n13, null, null, n6);
        assemble(n14, null, null, n7);
        assemble(n15, null, null, n7);

        System.out.println(Print(n1));
    }
}